/*
 * @作者: 沙昊
 * @邮箱: shahao@zju.edu.cn
 * @功能: 
 * @包含算法: 
 * Copyright (c) 2023 by 沙昊, All Rights Reserved. 
 */
#include <vector>
#include <iostream>

using namespace std;
int direction[2][2] = {1,0,0,1};
vector<vector<int>> path;
// vector<vector<int>> result;

bool dfs(vector<vector<int>>& map, vector<vector<bool>>& visited, vector<int> cur_index, vector<int> goal_index){
    if(cur_index[0]==goal_index[0] && cur_index[1]==goal_index[1]){
        // path.push_back(cur_index);
        // result = path;
        return true;
    }
    int m = map.size(), n= map[0].size();
    for(int i=0; i<2; i++){
        vector<int> next_index = cur_index;
        next_index[0] += direction[i][0];
        next_index[1] += direction[i][1];
        if(next_index[0]<0||next_index[0]>=m||next_index[0]<0||next_index[0]>=m||map[next_index[0]][next_index[1]]==1||visited[next_index[0]][next_index[1]]==true){
            continue;
        } 
        visited[next_index[0]][next_index[1]] = true;
        path.push_back(next_index);
        if(dfs(map, visited, next_index, goal_index)){
            return true;
        }
        else{
            visited[next_index[0]][next_index[1]] = false;
            path.pop_back();
        }

    }
    return false;
} 

int main(void){

    vector<vector<int>> map = {{0,0,0},{0,0,0},{0,1,0}};
    int m = map.size(), n = map[0].size();
    vector<int> start = {0,0};
    vector<int> goal = {m-1,n-1};
    vector<vector<bool>> visited(m,vector<bool>(n,false));
    visited[start[0]][start[1]] = true; 
    path.push_back(start);

    if(dfs(map, visited, start,goal)){
        for(int i=0; i<path.size(); i++){
            for(int j=0; j<path[0].size(); j++){
                cout<<path[i][j];
                // cout<<"sha";
            }
            cout<<endl;
            // cout<<"me"<<endl;
            // cout<<1<<endl;
        }
    }
    else{
        cout<<"no path"<<endl;
    }
    // cout<<path.size()<<path[0].size()<<endl;
    return 0;
}


//push_back(make_pair<>)